The present invention relates generally to a graphics transmission system and, more particularly, to a new and improved adaptive encoding method of, and apparatus for, efficiently encoding and decoding sequential data to reduce the transmission time and/or band width required to convey graphics reproduction indicia.
The art of facsimile or graphics band width compression for use in document reproduction and transmission systems is well known and a general discussion of the prior art can be found in the U.S. patents to Fleckenstein et al U.S. Pat. No. 2,909,601, Kagan et al U.S. Pat. No. 3,347,981 and Wernikoff et al U.S. Pat. No. 3,394,352. These systems are basically comprised of some type of facsimile scanner which scans a document to be transmitted for reproduction and supplies the results of the scanning operation to a data band width reduction encoding apparatus. The data encoding apparatus then produces encoded output signals which are related in the indicia appearing on the face of the document to be reproduced. The encoded signals are subsequently transmitted to a remote receiver which decodes the received signals and supplies the decoded information to a recorder which reproduces a facsimile of the original document.
One of the principal problems encountered in the use of graphics transmission apparatus is the time required to transmit the voluminous quantity of data required to enable an accurate reproduction to be made. In the prior art attempts to compress the transmitted data, various coding configurations and techniques have been used which are typically based upon the statistical probability of the scanned information remaining stationary, or the same, for at least a finite period of time.
In the above mentioned Wernikoff et al patent, for example, a method is described which can simultaneously evaluate the compression efficiency of several different encoders, and then identify the one that is able to represent the most recent portion of the scan with the smallest number of digits. The most efficient encoder is then selected and caused to transmit the compressed data. This technique is able to selectively assign encoders in any combination, such that the encoder used at any given time is the best choice for that portion of the scan. Although the Wernikoff solution provides improved compression efficiencies for a certain class of data, its potential is limited because the number of encoders which can be incorporated is finite and the high cost of including more than three or four different encoders to accommodate different data statistics in a single system makes this solution undesirable for most applications.
In the aforementioned Kagan disclosure, a method is described wherein the scanned indicia is produced by differentiating a graphics copy in both the X and Y directions. Since the spacing between indicia may typically be short or long, Kagan et al have employed a coding technique for using a long and a short binary code in any desired combination, and they distinguish or identify which code is being used by a prefix bit preceding the associated code.
This technique has been found to work well if the long code appears quite frequently, i.e., the separation between indicia frequently being large. However, the efficiency of this system will fall off quite rapidly if many short codes are required, thus indicating small separation between indicia. This loss in efficiency is due to the fact that the required prefix bit occupies a greater percentage of bandwith for the short code (approximately 33%) than for the long code (approximately 11%).
Furthermore, the device is committed to only two code lengths which under certain indicia conditions produce unsatisfactory operation. For example, if a 3-bit short code plus the prefix bit is used, and if the indicia is spaced two picture elements apart, the system requires twice the bandwith (or transmission time) which would otherwise be required without the data compression. To overcome this problem, Kagan et al states that more code combinations can be used by adding further prefix bits to identify the expanded code selection. This, of course, will further reduce the transmission efficiency.